【题解】 [SCOI2014]方伯伯的玉米田 树状数组优化DP luoguP3287 | Qiuly's blog!

【题解】 [SCOI2014]方伯伯的玉米田 树状数组优化DP luoguP3287

Posted on | Edited on | In | Comments:

以后不要被这种傻逼题给蒙骗了。传送门：方伯伯的传送门=。=

首先要明确一个道理，每一次拔高的右端点一定是 $n$ ，如果是只拔高中间部分，右边的又要尽可能大于中间部分，索性一起拔了，这一定是最优的。

设 $f_{i,j}$ 表示第 $i$ 个玉米被拔高了 $j$ 次时以 $i$ 结尾的最长不下降子序列长度，容易得出转移方程：

可能有人会问为什么 $l\leq j$ ，很显然就是上面的道理，越大的 $i$ 一定拔高次数是单调不减的。

发现上面的转移其实是 $O(n^2k^2)$ 的，万恶的出题人不会给这个复杂度一丁点分……这个时候用树状数组优化转移，发现上面有三个限制条件，我们正着枚举 $i$ ，就已经满足第一个条件了，因为这个时候树状数组中的都是小于 $i$ 的 $k$ 。然后将每个点按照 $(j+1,h_i+j)$ 放到平面上，然后树状数组统计答案即可。

树状数组维护的是 $\max$ ，不是和。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=1e4+2;
const int K=5e2+2;

int a[N],n,k,mx;
namespace BIT{
    int c[N][5009+K];
    void update(int x,int y,const int v) {
        for(;x<=mx+k;x+=(x&-x))for(int i=y;i<=k+1;i+=(i&-i))
                c[x][i]=max(c[x][i],v); 
    }
    int query(int x,int y) {
        int ans=0;
        for(;x;x-=(x&-x))for(int i=y;i;i-=(i&-i))
                ans=max(ans,c[x][i]);
        return ans;
    }
}using namespace BIT;

int main() {
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]),mx=max(mx,a[i]);
    int ans=0;
    for(int i=1;i<=n;++i)   
        for(int j=k;~j;--j) {
            int res=query(a[i]+j,j+1)+1;
            ans=max(ans,res),update(a[i]+j,j+1,res);
        }
    printf("%d\n",ans);
    return 0;
}

本文标题:【题解】 [SCOI2014]方伯伯的玉米田 树状数组优化DP luoguP3287

文章作者:Qiuly

发布时间:2019年05月04日 - 00:00

最后更新:2019年05月05日 - 10:25

原始链接:http://qiulyblog.github.io/2019/05/04/[题解]luoguP3287/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。